package greedy

import (
	myheap "traning/algorithm/utility/heap"
)

type Project struct {
	cost   int
	profit int
}

func (p Project)More (p1 myheap.Compare) bool {
	return p.profit > p1.(Project).profit
}

func (p Project)Less (p1 myheap.Compare) bool {
	return p.cost < p1.(Project).cost
}

func FindMaximizedCapital(projects []Project, hasMoney int, chance int) int {
	if len(projects) == 0 {
		return 0
	}
	return amxProfitProcess(projects, hasMoney, chance)
}

func amxProfitProcess(canDoProjects []Project, hasMoney, chance int) int {
	if chance == 0 {
		return hasMoney
	}
	ans := hasMoney
	for i, v := range canDoProjects {
		if hasMoney >= v.cost {
			ans = max(amxProfitProcess(copyAndExceptP(canDoProjects, i), hasMoney+v.profit-v.cost, chance-1), ans)
		}
	}
	return ans
}

func copyAndExceptP(canArrangeP []Project, exceptIndex int) []Project {
	ans := make([]Project, len(canArrangeP)-1)
	cur := 0
	for i,v := range canArrangeP {
		if i != exceptIndex {
			ans[cur] = v
			cur++
		}
	}
	return ans
}

func FindMaximizedCapital1 (projects []Project, hasMoney int, chance int) int {
	sheap := myheap.NewSmallHeap(len(projects))
	bheap := myheap.NewBigHeap(len(projects))
	for _, v := range projects {
		sheap.Push(v)
	}
	for i:=0; i<chance; i++ {
		for sheap.Size() > 0 && sheap.Peek().(Project).cost <= hasMoney {
			bheap.Push(sheap.Pop())
		}
		if bheap.Size() == 0 {
			break
		}
		dp := bheap.Pop().(Project)
		hasMoney -= dp.cost
		hasMoney += dp.profit
	}
	return hasMoney
}